package algorithmTopics.link;

import java.util.ArrayDeque;
import java.util.HashMap;

public class Solution {

    /**
     * 添加两个数字
     * 字最高位位于链表开始位置。它们的每个节点只存储一位数字。
     *
     * @param l1 l1
     * @param l2 l2
     * @return 将这两数相加会返回一个新的链表。
     */
    public ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
        //压入栈而已
        ArrayDeque<Integer> oneStack = new ArrayDeque<>();
        ArrayDeque<Integer> twoStack = new ArrayDeque<>();
        while (l1 != null) {
            oneStack.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            twoStack.push(l2.val);
            l2 = l2.next;
        }
        //拼接
        ListNode pre = null;
        int add = 0;
        while (!oneStack.isEmpty() || !twoStack.isEmpty() || add != 0) {
            int one = oneStack.isEmpty() ? 0 : oneStack.pop();
            int two = twoStack.isEmpty() ? 0 : twoStack.pop();
            int sum = (one + two + add);
            ListNode curr= new ListNode(sum % 10);
            curr.next = pre;
            pre = curr;
            add = sum / 10;
        }
        return pre;
    }




    /**
     * 合并k个升序链表 升序返回
     *
     * @param lists 列表
     * @return {@link ListNode}
     */
    public ListNode mergeKLists(ListNode[] lists) {
        // 方法一 分治
        // 方法二 可以用最小堆
        int len = lists.length;
        if (len < 2) {
            return null;
        }
        ListNode top = new ListNode(0);
        ListNode curr = top;
        ListNode left = lists[0];
        for (int i = 1; i < len; i++) {
            // 合并
            ListNode right = lists[i];
            while (left != null && right != null) {
                if (left.val < right.val) {
                    curr.next = left;
                    left = left.next;
                } else {
                    curr.next = right;
                    right = right.next;
                }
                curr = curr.next;
            }
            curr.next = left != null ? left : right;
            left = top.next;
            curr = top;
        }

        return top.next;

    }


    /**
     * 排序列表 升序
     *
     * @param head 封头
     * @return {@link ListNode}
     */
    public ListNode sortList(ListNode head) {

        // 归并排序
        if (head == null || head.next == null) {
            return head;
        }
        // 分治
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode temp = slow.next;
        slow.next = null;

        // 迭代
        ListNode left = sortList(head);
        ListNode right = sortList(temp);

        // 前置一个节点
        ListNode h = new ListNode(0);
        ListNode res = h;
        //合并
        while (left != null && right != null) {
            if (left.val < right.val) {
                h.next = left;
                left = left.next;
            } else {
                h.next = right;
                right = right.next;
            }
            h = h.next;
        }
        // 合并剩余
        h.next = left != null ? left : right;

        return res.next;
    }


    /**
     * 旧新 节点映射
     */
    private HashMap<Node, Node> oldNew = new HashMap<>();

    /**
     * 复制随机列表
     *
     * @param head 封头
     * @return {@link Node}
     */
    public Node copyRandomList(Node head) {
        // 遍历
        Node curr = head;
        while (curr != null) {
            // 创造新节点
            //创造映射关系
            oldNew.put(curr, new Node(curr.val));
            curr = curr.next;
        }
        // next random
        curr = head;
        while (curr != null) {
            oldNew.get(curr).next = oldNew.getOrDefault(curr.next, null);
            oldNew.get(curr).random = oldNew.getOrDefault(curr.random, null);
            curr = curr.next;
        }

        return oldNew.getOrDefault(head, null);
    }


    /**
     * 一次性交换 链表中的K个数，直到链表结束
     *
     * @param head 封头
     * @param k    k 每次交换个数
     * @return {@link ListNode}
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        // 求出链表长度
        int n = 0;
        ListNode curr = head;
        while (curr != null) {
            n++;
            curr = curr.next;
        }
        // 哨兵节点记录
        ListNode dummy = new ListNode(0, head);
        // 记录 需要翻转的链表的前置节点
        ListNode p0 = dummy;
        // curr 的上一个
        ListNode pre = null;
        curr = p0.next;
        while (n >= k) {
            n -= k;
            // 翻转k个节点
            for (int i = 0; i < k; i++) {
                ListNode next = curr.next;
                curr.next = pre;
                //更新pre  curr
                pre = curr;
                curr = next;
            }
            ListNode next = p0.next;

            // 指向curr
            p0.next.next = curr;
            // 指向翻转后的头
            p0.next = pre;
            p0 = next;
        }

        return dummy.next;
    }


    /**
     * 交换 链表 本身
     *
     * @param head 封头
     * @return {@link ListNode}
     */
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 交换next or head
        // 注重当前俩节点交换
        ListNode next = head.next;
        head.next = swapPairs(next.next);
        next.next = head;
        return next;
    }

    /**
     * 合并两个升序链表
     *
     * @param list1 列表1
     * @param list2 列表2
     * @return {@link ListNode}
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //递归
        if (list1 == null) {
            return list2;
        } else if (list2 == null) {
            return list1;
        } else if (list1.val <= list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }


    public boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }
        for (ListNode slow = head, fast = head.next; fast != null && fast.next != null; slow = slow.next, fast = fast.next.next) {
            if (slow == fast) {
                return true;
            }
        }

        return false;
    }

    /**
     * 有循环 在链表之中
     *
     * @param head 封头
     * @return boolean
     */
   /* public boolean hasCycle(ListNode head) {
        // 方法一
        ListNode curr = head;
        Set<ListNode> set = new HashSet<>();
        while(curr != null){
            if (set.contains(curr)) {
                return true;
            }
            set.add(curr);
            curr = curr.next;
        }

        return false;

    }*/

    /**
     * 是回文
     *
     * @param head 封头
     * @return boolean
     */
    public boolean isPalindrome(ListNode head) {
        //翻转在比较
        ListNode A = head;
        // 寻找中间的那个节点
        ListNode slow = A, fast = A;
        while (fast != null && fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode B = reverseList(slow);
        while (B != null && A != null) {
            if (A.val != B.val) {
                return false;
            }
            A = A.next;
            B = B.next;
        }

        return true;
    }

    /**
     * 反向列表
     *
     * @param head 头
     * @return {@link ListNode}
     */
    public ListNode reverseList(ListNode head) {
        ListNode curr = head;
        ListNode pre = null;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }

        return pre;
    }


    //力扣 两数字相加
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode listNodeRes = l2;
        //俩节点相加吧
        // 把链表1的数字都加入到链表2
        //要进的位数，最大就是1
        boolean isEnter = false;
        while (l1 != null) {
            //第二个链表不为空

            int num = isEnter ? l1.val + l2.val + 1 : l1.val + l2.val;
            if (num >= 10) {
                //下一次计算的时候需要进一位
                isEnter = true;
                l2.val = num % 10;
            } else {
                //否则就不需要进一位
                isEnter = false;
                l2.val = num;
            }
            if (l1.next == null && isEnter) {
                ListNode listNode = new ListNode(0);
                l1.next = listNode;
            }
            if (l2.next == null && l1.next != null) {
                ListNode listNode = new ListNode(0);
                l2.next = listNode;
            }

            l2 = l2.next;
            l1 = l1.next;
        }

        return listNodeRes;
    }

}
